package com.yohann.algorithm.prim;

import java.util.Arrays;

/**
 * <p>
 * prim算法(最小生成树)
 * </p>
 *
 * @author Yohann
 * @since 2021/1/20 18:26
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'};
        int verxs = data.length;
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}
        };

        MapGraph graph = new MapGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);

        minTree.showGraph(graph);
        minTree.prim(graph, 4);
    }
}

class MinTree {
    public void createGraph(MapGraph graph, int verxs, char[] data, int[][] weight) {
        for (int i = 0; i < verxs; i++) {
            graph.data[i] = data[i];
            System.arraycopy(weight[i], 0, graph.weight[i], 0, verxs);
        }
    }

    public void showGraph(MapGraph graph) {
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    public void prim(MapGraph graph, int v) {
        int[] visited = new int[graph.verxs];

        //标记已访问
        visited[v] = 1;
        //记录两个顶点
        int h1 = -1;
        int h2 = -1;

        //初始化最大数
        int miniWeight = 10000;

        //n-1条边
        for (int i = 1; i < graph.verxs; i++) {
            for (int j = 0; j < graph.verxs; j++) {
                for (int k = 0; k < graph.verxs; k++) {
                    if (visited[j] == 1 && visited[k] == 0 && graph.weight[j][k] < miniWeight) {
                        //寻找距离最小节点
                        miniWeight = graph.weight[j][k];
                        h1 = j;
                        h2 = k;
                    }
                }
            }
            System.out.println(String.format("边<%s, %s> 权值:%s", graph.data[h1], graph.data[h2], miniWeight));
            //标记已访问节点
            visited[h2] = 1;
            miniWeight = 10000;
        }
    }
}

class MapGraph {
    //节点个数
    int verxs;
    //节点数据
    char[] data;
    //存放边 邻接矩阵
    int[][] weight;

    public MapGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}